﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Maze_tools
{
    public class sum_n
    {
        public static int sum(int c)
        {
            int k = 0;
            for (int i = 0; i < 4; ++i)
            {
                if ((c & (1 << i)) == (1 << i))
                    ++k;
            }
            return k;
        }
    }
    public struct Point
    {
        public int x;
        public int y;
    };
    public class Ground
    {
        protected int n, m;
        public void set_size(int i, int j)
        {
            n = i;
            m = j;
        }
    }
    public class Maze : Ground
    {
        private Stack<Point> st = new Stack<Point>();
        private int[,] weight = new int [100,100];
        private int si, sj;
        int[,] map = new int [100,100];
        Point start, finish, current;
        public void init_maze()
        {
            start.x = -1;
            start.y = 0;
            finish.x = -1;
            finish.y = m - 1;
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                {
                    map[i, j] = 0;
                }
        }
        public void generate()
        {
            Point buffer, b1;
            Random r = new Random();
            int d;
            start.x = r.Next(n);
            start.y = 0;
            current = start;
            finish.x = -1;
            finish.y = -1;
            st.Push(start);
            while (st.Count() > 0 && finish.x==-1)
            {
                bool exist;
                buffer = st.Peek();
                b1 = buffer;
                map[buffer.x, buffer.y] = (map[buffer.x, buffer.y] | (1 << 4)); //made it visited
                int time = 0;
                while (true)
                {
                    ++time;
                    d = ((r.Next(4) + r.Next(4)) * 147) % 4;
                    exist = true;
                    switch (d)
                    {
                        case 0:
                            if (b1.y + 1 < m)
                                ++b1.y;
                            else
                                exist = false;
                            break;
                        case 1:
                            if (b1.x - 1 >= 0)
                                --b1.x;
                            else
                                exist = false;
                            break;
                        case 2:
                            if (b1.y - 1 >= 0)
                                --b1.y;
                            else
                                exist = false;
                            break;
                        case 3:
                            if (b1.x + 1 < n)
                                ++b1.x;
                            else
                                exist = false;
                            break;
                    }
                    if (exist)
                    {
                        if (((map[b1.x, b1.y] & (1 << 4)) != (1 << 4)) && (sum_n.sum(map[b1.x, b1.y]) < 3) && (sum_n.sum(map[buffer.x, buffer.y]) < 3))
                        {
                            map[buffer.x, buffer.y] = (map[buffer.x, buffer.y] | (1 << d)); //mark new neighbour
                            switch (d)
                            {
                                case 0: d = 2; break;
                                case 1: d = 3; break;
                                case 2: d = 0; break;
                                case 3: d = 1; break;
                            }
                            map[b1.x, b1.y] = (map[b1.x, b1.y] | (1 << d)); //mark new neighbour
                            map[b1.x, b1.y] = (map[b1.x, b1.y] | (1 << 4)); //made it visited
                            buffer = b1;
                            break;
                        }
                        else
                        {
                            break;
                        }
                    }
                    if (time > 4 || sum_n.sum(map[buffer.x, buffer.y]) >= 3)
                    {
                        break;
                    }
                }
                if (b1.y == m - 1)
                {
                    finish.x = b1.x;
                    finish.y = b1.y;
                    map[b1.x, b1.y] = (map[b1.x, b1.y] | (1 << 4)); //made it visited
                }

                int p = 0;
                if (buffer.y + 1 >= m) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 0)) == (1 << 0)) ++p;
                if (buffer.x - 1 < 0) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 1)) == (1 << 1)) ++p;
                if (buffer.y - 1 < 0) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 2)) == (1 << 2)) ++p;
                if (buffer.x  + 1 >= n) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 3)) == (1 << 3)) ++p;

                if (finish.x == -1 && p!=4
            && sum_n.sum(map[buffer.x, buffer.y]) < 4 /*&& time < 4*/) 
                    st.Push(b1);
                else
                    if (st.Count() > 0)
                        st.Pop();
            }
            ////////////////////////////////Finished generating main hall
        }
        public void add_more_halls(int i, int j)
        {
            Point buffer, b1, inp;
            inp.x = i;
            inp.y = j;
            Random r = new Random();
            int d;
            st.Push(inp);
            while (st.Count() > 0)
            {
                buffer = st.Peek();
                b1 = buffer;
                map[buffer.x, buffer.y] = (map[buffer.x, buffer.y] | (1 << 4)); //made it visited
                int time = 0;

                while (true)
                {
                    ++time;
                    d = (r.Next(4) + 1 + r.Next(4)) % 4;
                    bool exist = true;
                    switch (d)
                    {
                        case 0:
                            if (b1.y + 1 < m)
                                ++b1.y;
                            else
                                exist = false;
                            break;
                        case 1:
                            if (b1.x - 1 >= 0)
                                --b1.x;
                            else
                                exist = false;
                            break;
                        case 2:
                            if (b1.y - 1 >= 0)
                                --b1.y;
                            else
                                exist = false;
                            break;
                        case 3:
                            if (b1.x + 1 < n)
                                ++b1.x;
                            else
                                exist = false;
                            break;
                    }
                    if (exist)
                    {
                        if (((map[b1.x, b1.y] & (1 << 4)) != (1 << 4)) && (sum_n.sum(map[b1.x, b1.y]) < 3) && (sum_n.sum(map[buffer.x, buffer.y]) < 3))
                        {
                            map[buffer.x, buffer.y] = (map[buffer.x, buffer.y] | (1 << d)); //mark new neighbour
                            switch (d)
                            {
                                case 0: d = 2; break;
                                case 1: d = 3; break;
                                case 2: d = 0; break;
                                case 3: d = 1; break;
                            }
                            map[b1.x, b1.y] = (map[b1.x, b1.y] | (1 << d)); //mark new neighbour
                            map[b1.x, b1.y] = (map[b1.x, b1.y] | (1 << 4)); //made it visited
                            buffer = b1;
                        }
                    }
                    if (time > 4 || sum_n.sum(map[buffer.x, buffer.y]) >= 3)
                    {
                        break;
                    }
                }
                int p = 0;
                if (buffer.y + 1 >= m) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 0)) == (1 << 0)) ++p;
                if (buffer.x - 1 < 0) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 1)) == (1 << 1)) ++p;
                if (buffer.y - 1 < 0) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 2)) == (1 << 2)) ++p;
                if (buffer.x + 1 >= n) ++p;
                else
                    if ((map[buffer.x, buffer.y] & (1 << 3)) == (1 << 3)) ++p;
                if (p!=4 && sum_n.sum(map[buffer.x, buffer.y]) < 3 && time < 4)
                    st.Push(b1);
                else
                    if (st.Count()>0)
                        st.Pop();
            }
            ////////////////////////////////Finished generating additional halls
        }
        public void move_to(int dir)
        {
            if ((map[current.x,current.y] & (1<<dir)) == (1<<dir))
            {
                switch (dir)
                {
                    case 0:
                        if (current.y + 1 < m) 
                            ++current.y;
                        break;
                    case 1:
                        if (current.x - 1 >= 0)
                            --current.x;
                        break;
                    case 2:
                        if (current.y - 1 >= 0) 
                            --current.y;
                        break;
                    case 3:
                        if (current.x + 1 < n)
                            ++current.x;
                        break;
                }
            }
        }
        public int count_length()
        {
            Point cell, buf;
            const int inf = (1 << 16);
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                    weight[i, j] = inf;
            int[] i_direct = { 0, -1, 0, 1 };
            int[] j_direct = { 1, 0, -1, 0 };
            si = start.x;
            sj = 0;
            weight[si, sj] = 0;

            cell.x = si;
            cell.y = sj;
            st.Push(cell);
            int l;
            while (st.Count() > 0)
            {
                cell = st.Peek();
                buf = cell;
                st.Pop();
                for (l = 0; l < 4; ++l)
                    if (cell.x + i_direct[l] >= 0 && cell.x + i_direct[l] < n && cell.y + j_direct[l] > 0 && cell.y + j_direct[l]<m)
                    if ((map[cell.x, cell.y] & (1 << l)) == (1 << l))
                    {
                        if (weight[cell.x + i_direct[l], cell.y + j_direct[l]] < weight[cell.x, cell.y] + 1)
                        {
                            buf.x = cell.x + i_direct[l];
                            buf.y = cell.y + j_direct[l];
                            st.Push(buf);
                        }
                            
                        weight[cell.x + i_direct[l], cell.y + j_direct[l]] = Math.Min(weight[cell.x + i_direct[l], cell.y + j_direct[l]], weight[cell.x, cell.y] + 1);                    }

            }
            return weight[finish.x, finish.y];
        }
        public void check_maze()
        {
            int[] i_direct = { 0, -1, 0, 1 };
            int[] j_direct = { 1, 0, -1, 0 };
            for (int i=0; i<n; ++i)
                for (int j = 0; j < m; ++j)
                    for (int l = 0; l < 4; ++l)
                    {
                        if (i+i_direct[l]>=0 && i+i_direct[l]<n
                            && j+j_direct[l]>=0 && j+j_direct[l]<m)
                            if ((map[i, j] & (1 << l)) == (1 << l))
                            {
                                int dr = (l + 2) % 4;
                                map[i + i_direct[l], j + j_direct[l]] = map[i + i_direct[l], j + j_direct[l]] | (1 << dr);
                            }
                    }
        }
        public bool win()
        {
            if ((current.x == finish.x) && (current.y == finish.y))
                return true;
            else
                return false;
        }
        public Point get_cur_loc()
        {
            return current;
        }
        public Point get_finish_loc()
        {
            return finish;
        }
        public int get_cur_val(int i, int j)
        {
            return map[i, j];
        }
        public void write_maze()
        {
            StreamWriter sw = new StreamWriter("maze.txt");
            sw.WriteLine(n+" "+m);
            sw.WriteLine(current.x+" "+current.y+" "+finish.x+" "+finish.y);
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < m; ++j)
                    sw.Write(map[i,j]+" ");
                sw.WriteLine();
            }
            sw.Close();
        }
        public void read_maze()
        {
            StreamReader sr = new StreamReader("maze.txt");
            string[] tokens = sr.ReadLine().Split(' ');
            n = int.Parse(tokens[0]);
            m = int.Parse(tokens[1]);
            tokens = sr.ReadLine().Split(' ');
            current.x = int.Parse(tokens[0]);
            current.y = int.Parse(tokens[1]);
            finish.x = int.Parse(tokens[2]);
            finish.y = int.Parse(tokens[3]);
            for (int i = 0; i < n; ++i)
            {
                tokens = sr.ReadLine().Split(' ');
                for (int j = 0; j < m; ++j)
                    map[i,j] = int.Parse(tokens[j]);
            }
            sr.Close();
        }
    }
    public class Total
    {
        int moves=0;
        public void clear_all()
        {
            moves = 0;
        }
        public void load_moves(int mov)
        {
            moves = mov;
        }
        public void increment()
        {
            ++moves;
        }
        public int get_moves()
        {
            return moves;
        }
        public int evaluate(int pat)
        {
            double r = Convert.ToDouble(pat);
            double k = Convert.ToDouble(moves);
            return Convert.ToInt32(r / k * 1000000);
        }
        public void save_moves()
        {
            StreamWriter sw = new StreamWriter("moves.txt");
            sw.WriteLine(moves);
            sw.Close();
        }
        public void load_moves()
        {
            StreamReader sr = new StreamReader("maze.txt");
            string[] tokens = sr.ReadLine().Split(' ');
            moves = int.Parse(tokens[0]);
            sr.Close();
        }
    }
    public class Winners
    {
        int score;
        string name="";
        public void fwrite_name()
        {
            StreamWriter sw = new StreamWriter("results.txt",true);
            sw.WriteLine(name);
            sw.Close();
        }
        public void fwrite_score()
        {
            StreamWriter sw = new StreamWriter("results.txt",true);
            sw.WriteLine(score);
            sw.Close();
        }
        public void take_name(string s)
        {
            name = s;
        }
        public void take_score(int s)
        {
            score = s;
        }
    }
}
